package com.linzm.leetcode.primary.exercises2_20230116;

import java.util.Arrays;

/**
 * @Author zimingl
 * @Date 2023/1/20 23:38
 * @Description: 增减字符串匹配
 *
 * int n = s.length(), lo = 0, hi = n;  perm[i] = s.charAt(i) == 'I' ? lo++ : hi--;
 */
public class Demo15_942 {
    /**
     * 由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
     * 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
     * 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'
     * 给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
     * 输入：s = "IDID"
     * 输出：[0,4,1,3,2]
     * IIII 01234
     * DDDD 43210
     */
    public static void main(String[] args) {
        Demo15_942 demo15_942 = new Demo15_942();
        String s = "IDID";
        int[] ints = demo15_942.diStringMatch(s);
        String[] strings = Arrays.stream(ints).mapToObj(String::valueOf).toArray(String[]::new);
        System.out.println(String.join(" ", strings));
    }

    private int[] diStringMatch(String s) {
        int n = s.length(), lo = 0, hi = n;
        int[] perm = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            perm[i] = s.charAt(i) == 'I' ? lo++ : hi--;
        }
        perm[n] = lo; // 最后剩下一个数，此时 lo == hi
        return perm;
    }
}
